package subject.dp;

public class numSquares {

    public int numSquares1(int n) {
        // 创建DP数组：f[i]表示组成i所需的最少平方数个数
        int[] f = new int[n + 1];

        // 从1到n逐个计算
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE; // 初始化最小值

            // 尝试所有可能的平方数 j*j（j从1开始，j*j <= i）
            for (int j = 1; j * j <= i; j++) {
                // 核心：比较 f[i - j*j] 的值，寻找最小值
                minn = Math.min(minn, f[i - j * j]);
            }

            // 状态转移：最小值 + 1（当前使用的j*j）
            f[i] = minn + 1;
        }
        return f[n]; // 返回目标值的结果
    }
}
